package DataStructure.graph;

public class DepthFirstSearch {
    //索引代表顶点，值代表当前是否已经被搜索
    private boolean[] marked;
    //记录有多少个顶点与s顶点相通
    private int count;

    //找出Graph图中s顶点的所有相邻顶点
    public DepthFirstSearch(Graph G,int s){
        this.marked=new boolean[G.V()];
        this.count=0;
        dfs(G,s);
    }

    //使用深度优先搜索找出G图中v顶点的所有相通顶点
    public void dfs(Graph G,int v){
        //把v顶点标识为已搜索
        marked[v]=true;
        for (Integer w:G.adj(v)) {
            //判断当前w顶点有没有被搜索过，如果没有则递归调用dfs
            if(!marked[w]){
                dfs(G,w);
            }
        };
        count++;
    }


    //判断w和s是否想通
    public boolean marked(int w){
        return marked[w];
    }

    //获取与顶点s想通的所有顶点的总数
    public int count(){
        return count;
    }
}
